package algorithm.leetcode.I101to200;

import java.util.LinkedList;
import java.util.List;


/**
 * 勉强AC,时间复杂度非常高
 * T(n^2)+T(2^n) ~ O(2^n)
 */

public class Q131 {

    public List<List<String>> partition(String s) {
        boolean[][] isHuiWen = new boolean[s.length()][s.length()];
        for (int i = s.length()-1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (i == j) isHuiWen[i][j] = true;
                else if (j - i == 1) isHuiWen[i][j] = s.charAt(i) == s.charAt(j);
                else isHuiWen[i][j] = isHuiWen[i+1][j-1] && s.charAt(i) == s.charAt(j);
            }
        }

        List<List<String>> res = new LinkedList<>();
        // dfs复杂度为O(2^n)
        dfs(res, new LinkedList<>(), 0, s, isHuiWen);
        return res;
    }

    private void dfs(List<List<String>> total,
                     LinkedList<String> curr,
                     int start,
                     String s,
                     boolean[][] isHuiWen) {

        if (start >= s.length()) {
            total.add(new LinkedList<>(curr));
            return;
        }

        int tryLength = s.length() - start;
        for (int i = 1; i <= tryLength; i++) {
            if (isHuiWen[start][start+i-1]) {
                curr.add(s.substring(start, start+i));
                dfs(total, curr, start+i, s, isHuiWen);
                curr.removeLast();
            }
        }

    }

    public static void main(String[] args) {
        Q131 q131 = new Q131();
        System.out.println(q131.partition("a"));
    }
}
